﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// 原题连接：
/*
题目描述：
给定二叉树的根节点 root ，返回所有左叶子之和。

 

示例 1：



输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:

输入: root = [1]
输出: 0
 

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000
*/

// 开始解题：
// 方法1——向左边递归

typedef struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
	
} TreeNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
TreeNode* BinaryTreeCreate(int* tree, int treeSize, int* pi) {
    if ((*pi) == treeSize) {
        return NULL;
    }
    if (NULL == tree) {
        return NULL;
    }
    if (-1 == tree[*pi]) {
        (*pi)++;
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    if (NULL == root) {
        perror("malloc fail!\n");
        exit(-1);
    }
    root->val = tree[*pi];
    (*pi)++;
    root->left = BinaryTreeCreate(tree, treeSize, pi);
    root->right = BinaryTreeCreate(tree, treeSize, pi);
    return root;
}





bool isLeaves(struct TreeNode* root) {
    if (NULL == root) {
        return false;
    }
    return NULL == root->left && NULL == root->right;
}
int _sumOfLeftLeaves(struct TreeNode* root) {
    if (NULL == root) {
        return 0;
    }
    if (NULL == root->left && NULL == root->right) {
        return root->val;
    }
    if (isLeaves(root->right)) {
        return _sumOfLeftLeaves(root->left);
    }
    return _sumOfLeftLeaves(root->left) + _sumOfLeftLeaves(root->right);
}

int sumOfLeftLeaves(struct TreeNode* root) {
    if (isLeaves(root)) {
        return 0;
    }
    return _sumOfLeftLeaves(root);
}

int main() {
    int tree[] = { 3,9,20,-1,-1,15,7 };
    int treeSize = sizeof(tree) / sizeof(tree[0]);
    TreeNode* root = NULL;
    int i = 0;
    root = BinaryTreeCreate(tree, treeSize, &i);
    printf("%d\n", sumOfLeftLeaves(root));
	return 0;
}